//
//  main.swift
//  数据结构与算法
//
//  Created by 深圳链上时代 on 2020/11/18.
//

import Foundation

func test() {
    offer_54()
}
test()

// MARK: - 二叉树
func binaryTreeDemo() {
    let root = BinaryTreeNode("A")
    root.leftNode = {
        let node = BinaryTreeNode("B")
        node.leftNode = BinaryTreeNode("D")
        node.rightNode = BinaryTreeNode("E")
        return node
    }()
    root.rightNode = {
        let node = BinaryTreeNode("C")
        node.leftNode = BinaryTreeNode("F")
        node.rightNode = BinaryTreeNode("G")
        return node
    }()
    
//    // 前序遍历
//    preOrder(root)
    
//    // 中序遍历
//    inOrder(root)
    
//    // 后序遍历
//    postOrder(root)
    
    // bfs 按层遍历，广度优先遍历
    bfsOrder(root)
}

/// 二叉搜索树
func binarySearchTreeDemo() {
    let binarySearchTree = BinarySearchTree()
    
    for item in [9, 4, 1, 3, 2, 5, 6, 7, 8, 0] {
        binarySearchTree.inset(item)
    }
    
    binarySearchTree.delete(2)
    
    inOrder(binarySearchTree.tree!)
}

// MARK: - 前缀树
func treeNodeDemo() {
    let root = TreeNode(label: " ")
    root.add(word: "apple", exp: "苹果")
    root.add(word: "banner", exp: "香蕉")
    root.add(word: "cat", exp: "猫")
    root.add(word: "dog", exp: "狗")

    print(root.search(word: "dog") ?? "未找到该单词")

    // 深度优先搜索
    dfsByStack(root: root)

    let trie = Trie();

    trie.insert("apple")
    print(trie.search("apple")) // 返回 true
    //print(trie.search("app")) // 返回 false
    print(trie.startsWith("a")) // 返回 true
    //trie.insert("app")
    //print(trie.search("app"))     // 返回 true
}

// MARK: - 广度优先搜索
func bfsDemo() {
    var userNodes = [Node]()
    // 生成所有表示用户的结点
    for i in 0..<100 {
        userNodes.append(Node(userId: i))
    }
    // 生成所有表示用户的边
    for _ in 0..<userNodes.count {
        let aFriendId = arc4random_uniform(UInt32(userNodes.count))
        let bFriendId = arc4random_uniform(UInt32(userNodes.count))
        if aFriendId == bFriendId { continue }
        userNodes[Int(aFriendId)].friends!.insert(userNodes[Int(bFriendId)])
        userNodes[Int(bFriendId)].friends!.insert(userNodes[Int(aFriendId)])
    }
    
    bfs(userNodes: userNodes, userId: 50)
}

// MARK: - 堆
func heapDemo() {
//    var heap = Heap<Int>(10)
//    heap.inset(5)
//    heap.inset(1)
//    heap.inset(8)
//    heap.inset(7)
//    heap.removeMax()
//    print(heap)
    var a = [nil, 9, 4, 1, 3, 2, 5, 6, 7, 8, 0]
    Heap<Int>.sort(&a, a.count - 1)
    print(a)
}
